package LearnAlgorithm.j_动态规划and贪心算法;

import java.util.Scanner;

/*
数字三角形(POJ1163)

在数字三角形中寻找一条从顶部到底边的路径，使得路径上所经过的数字之和最大。
路径上的每一步都只能往左下或 右下走。只需要求出这个最大和即可，不必给出具体路径。

三角形的行数大于1小于等于100，数字为 0 - 99

输入格式：
//5表示三角形的行数,接下来输入三角形
in
5		
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

out
30
要求输出最大和
 */

public class h数字三角形最大路径值byDFS记忆性递归 {
	public static void main(String[] args) {
		h数字三角形最大路径值byDFS记忆性递归 test = new h数字三角形最大路径值byDFS记忆性递归();
		test.useDFS();
	}
	
	/**
	 * 前置方法
	 */
	public void useDFS() {
		Scanner scanner = new Scanner(System.in);
		int N = scanner.nextInt();
		int[][] triangle = new int[N][];
		int[][] recall = new int[N][];//备忘录初始所有元素为-1
		for (int i = 0; i < N; i++) {
			triangle[i] = new int[i + 1];
			recall[i] = new int[i + 1];
			for (int j = 0; j < i + 1; j++) {
				triangle[i][j] = scanner.nextInt();
				recall[i][j] = -1;
			}
		}
		int res = DFS(N, triangle, recall, 0, 0);
		System.out.println(res);
	}
	
	/**
	 * 记忆性递归
	 * @param N
	 * @param triangle
	 * @param recall
	 * @param row
	 * @param col
	 * @return
	 */
	public int DFS(int N, int[][] triangle, int[][] recall, int row, int col) {
		int left = -1;
		int right = -1;
		int res = -1;
		if (row == N - 1) {//如果递归到最后一层，直接输出该元素；递归出口
			return triangle[row][col];
		} else {
			if (recall[row + 1][col] == -1) {//左孩子；如果备忘录中存在，就不必递归
				left = DFS(N, triangle, recall, row + 1, col);
			} else {
				left = recall[row + 1][col];
			}
			if (recall[row + 1][col + 1] == -1) {//右孩子；如果备忘录中存在，就不必递归
				right = DFS(N, triangle, recall, row + 1, col + 1);
			} else {
				right = recall[row + 1][col + 1];
			}
			res = triangle[row][col] + Math.max(left, right);//当前节点数值 + 两孩子中最大的
		}
		recall[row][col] = res;//存入备忘录
		return res;
	}
}
